package ms.sudoku;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import ms.sudoku.technique.EliminationTechnique;
import ms.sudoku.technique.NakedSingleTechnique;
import ms.sudoku.util.IntSet;
import ms.sudoku.util.RandomHelper;

import org.lex.game.sudoku.model.Point;

import common.Difficulty;
import common.Sudokus;

//Description: Sudoku puzzle solver.
public final class Solver {
	private Solver() {
	}

	/**
	 * Evaluates the difficulty level of a particular puzzle.
	 */
	public static Difficulty evaluateDifficulty(PuzzleState state) {
		if (state == null) {
			throw new NullPointerException("state is null");
		}

		SolverOptions solverOption = new SolverOptions();
		for (Difficulty level : new Difficulty[] { Difficulty.Easy, Difficulty.Medium, Difficulty.Hard }) {
			GeneratorOptions generatorOption = GeneratorOptions.create(level);
			if (state.getFilledCellCount() < generatorOption.getMinFilledCells()) {
				continue;
			}

			solverOption.setAllowBruteForce(generatorOption.getDecisionPoints() > 0);
			solverOption.setEliminationTechniques(generatorOption.getAllowedTechniques());
			solverOption.setMaximumSolutionsToFind(solverOption.getAllowBruteForce() ? 2 : 1);

			SolverResults solverResult = Solver.solve(state, solverOption);
			if (solverResult.getStatus() == PuzzleStatus.Solved && solverResult.getPuzzles().size() == 1) {
				return level;
			}
		}
		return Difficulty.Invalid;
	}

	/**
	 * Attempts to solve a Sudoku puzzle.Returns>The result of the solve
	 * attempt.<br>
	 * No changes are made to the parameter state.
	 */
	public static SolverResults solve(PuzzleState state, SolverOptions solverOption) {
		boolean techniqueIsEmpty = false;

		if (solverOption.getEliminationTechniques().isEmpty()) {
			solverOption.getEliminationTechniques().add(new NakedSingleTechnique());
			techniqueIsEmpty = true;
		}

		// Attempt to solve the puzzle
		SolverResults solverResults = solveInternal(state, solverOption);

		if (true == techniqueIsEmpty) {
			solverOption.getEliminationTechniques().clear();
		}

		// Return the solver results
		return solverResults;
	}

	private static SolverResults solveInternal(PuzzleState state, SolverOptions options) {
		/*
		 * First, make a copy of the state and work on that copy. That way, the
		 * original instance passed to us by the client remains unmodified.
		 */
		state = state.clone();

		/*
		 * Fill cells using logic and analysis techniques until no more can be
		 * filled.
		 */
		Map<EliminationTechnique, Integer> totalUseOfTechniques = new HashMap<>();
		IntSet[][] possibleNumbers = fillCellsWithSolePossibleNumber(state, options.getEliminationTechniques(),
				totalUseOfTechniques);

		// Analyze the current state of the board
		switch (state.getStatus()) {
		/*
		 * If the puzzle is now solved, return it. If the puzzle is in an
		 * inconsistent state (such as two of the same number in the same row),
		 * return that also, as there's nothing more to be done.
		 */
		case Solved:
		case CannotBeSolved:
			return new SolverResults(state.getStatus(), state, 0, totalUseOfTechniques);
			/*
			 * If the puzzle is still in progress, it means no more cells can be
			 * filled by elimination alone, so do a brute-force step.
			 * BruteForceSolve recursively calls back to this method.
			 */
		default:
			if (options.getAllowBruteForce()) {
				SolverResults results = bruteForceSolve(state, options, possibleNumbers);
				if (results.getStatus() == PuzzleStatus.Solved) {
					addTechniqueUsageTables(results.getUseOfTechniques(), totalUseOfTechniques);
				}
				return results;
			} else
				return new SolverResults(PuzzleStatus.CannotBeSolved, state, 0, null);

		}
	}

	/**
	 * Uses brute-force search techniques to solve the puzzle. Return The result
	 * of the solve attempt.<br>
	 * Changes may be made to the parameter state.
	 */
	private static SolverResults bruteForceSolve(PuzzleState state, SolverOptions options, IntSet[][] possibleNumbers) {
		/*
		 * A standard brute-force search would take much too long to solve a
		 * Sudoku puzzle. Fortunately, there are ways to significantly trim the
		 * search tree to a point where brute-force is not only possible, but
		 * also more efficient. The idea is that not every number can be put
		 * into every cell. In fact, using elimination techniques, you can
		 * narrow down the list of numbers for each cell, such that only those
		 * need be are tried. Moreover, every time a new number is entered into
		 * a cell, other cell's possible numbers decrease. It's in your best
		 * interest to start the search with a cell that has the least possible
		 * number of options, thereby increasing your chances of "guessing" the
		 * right number sooner. To this end, you find the cell in the grid that
		 * is empty and that has the least number of possible numbers that can
		 * go in it. If there is more than one cell with the same number of
		 * possibilities, you choose randomly among them. This random choice
		 * allows the solver to be used for puzzle generation.
		 */
		int gridSize = state.getGridSize();
		List<Point> bestGuessCells = new ArrayList<>();
		int bestNumberOfPossibilities = gridSize + 1;
		for (int i = 0; i < gridSize; i++) {
			for (int j = 0; j < gridSize; j++) {
				int count = possibleNumbers[i][j].size();
				if (Sudokus.isEmpty(state.get(i, j))) {
					if (count < bestNumberOfPossibilities) {
						bestNumberOfPossibilities = count;
						bestGuessCells.clear();
						bestGuessCells.add(new Point(i, j));
					} else if (count == bestNumberOfPossibilities) {
						bestGuessCells.add(new Point(i, j));
					}

				}

			}
		}

		/*
		 * If there are no cells available to fill, there is nothing you can do
		 * to make forward progress. If there are cells available, which should
		 * always be the case when this method is called, go through each of the
		 * possible numbers in the cell and try to solve the puzzle with that
		 * number in it.
		 */
		SolverResults results = null;
		if (bestGuessCells.size() > 0) {
			// Choose a random cell from amongst the possibilities found above
			Point bestGuessCell = bestGuessCells.get(new RandomHelper().getRandomNumber(bestGuessCells.size()));

			/*
			 * Get the possible numbers for that cell. For each possible number,
			 * fill that number into the cell and recursively call to Solve.
			 */
			IntSet possibleNumbersForBestCell = possibleNumbers[bestGuessCell.x][bestGuessCell.y];
			for (int p = 0; p < possibleNumbersForBestCell.capacity(); p++) {
				if (possibleNumbersForBestCell.contains(p)) {
					PuzzleState newState = state;

					// Fill in the cell and solve the puzzle
					newState.setCell(bestGuessCell, p);
					SolverOptions tempOptions = options.clone();
					if (results != null) {
						tempOptions.setMaximumSolutionsToFind((tempOptions.getMaximumSolutionsToFind() - results
								.getPuzzles().size()));
					}

					SolverResults tempResults = solveInternal(newState, tempOptions);
					/*
					 * If it could be solved, update information about the
					 * solving process and return the solution. Only if the user
					 * wants to find multiple solutions will the search
					 * continue.
					 */
					if (tempResults.getStatus() == PuzzleStatus.Solved) {
						if (results != null && results.getPuzzles().size() > 0) {
							results.getPuzzles().addAll(tempResults.getPuzzles());
						} else {
							results = tempResults;
							results.setNumberOfDecisionPoints(results.getNumberOfDecisionPoints() + 1);
						}
						if (options.getMaximumSolutionsToFind() > 0
								&& results.getPuzzles().size() >= options.getMaximumSolutionsToFind())
							return results;

					}
					// If you are not cloning, you need to cancel out the change
					newState.setCell(bestGuessCell, Sudokus.EMPTY_NUMBER);
				}

			}
		}

		return results != null ? results : new SolverResults(PuzzleStatus.CannotBeSolved, state, 0, null);
	}

	private static void addTechniqueUsageTables(Map<EliminationTechnique, Integer> totalTable,
			Map<EliminationTechnique, Integer> incrementalTable) {
		if (totalTable != null && incrementalTable != null) {
			for (Map.Entry<EliminationTechnique, Integer> entry : incrementalTable.entrySet()) {
				Integer valueInTotalTable = totalTable.get(entry.getKey());
				Integer valueInIncreTable = entry.getValue();
				Integer newTotalValue = valueInTotalTable != null ? valueInIncreTable + valueInTotalTable
						: valueInIncreTable;
				totalTable.put(entry.getKey(), newTotalValue);
			}
		}
	}

	/**
	 * Attempts to fill one square in the Sudoku puzzle, based purely on logic
	 * and elimination techniques. Return the current set of possible numbers
	 * for each cell.<br>
	 * Changes may be made to the parameter state.
	 */
	private static IntSet[][] fillCellsWithSolePossibleNumber(PuzzleState state, List<EliminationTechnique> techniques,
			Map<EliminationTechnique, Integer> totalUseOfTechniques) {
		int gridSize = state.getGridSize();
		IntSet[][] possibleNumbers = new IntSet[gridSize][gridSize];
		for (int row = 0; row < gridSize; row++) {
			possibleNumbers[row] = new IntSet[gridSize];
			for (int col = 0; col < gridSize; col++) {
				possibleNumbers[row][col] = new IntSet(gridSize);
			}
		}
		boolean moreToDo = false;
		do {
			moreToDo = false;
			state.computePossibleNumbers(techniques, totalUseOfTechniques, false, false, possibleNumbers);

			for (int row = 0; row < gridSize; row++) {
				for (int col = 0; col < gridSize; col++) {
					if (Sudokus.isEmpty(state.get(row, col)) && possibleNumbers[row][col].size() == 1) {
						for (int n = 0; n < gridSize; n++) {
							if (possibleNumbers[row][col].contains(n)) {
								state.set(row, col, n);
								moreToDo = true;
								break;
							}
						}
					}
				}
			}
		} while (moreToDo);
		return possibleNumbers;
	}
}
